\section{Proposition de solution au problème de comparaison}
\label{solution_compare_graphs}

En section~\ref{prob-comp-graph}, nous avons vu que notre problème ne pouvait pas avoir de solution polynomiale (sauf si $P = NP$). Nous avons également dit que certaines simplifications peuvent être apportées et qu'avec ces simplifications, l'exécution de la solution, en pratique, peut se faire en un temps acceptable. Nous allons proposer, dans cette section, deux idées de simplification, avant de faire un état de l'art des travaux effectués dans le domaine de comparaison de graphes. Ces idées de simplifications viennent de la raison pour laquelle les temps d'exécutions des algorithmes proposés dans la littérature augmentent de manière exponentielle: le nombre de n\oe{}uds. Donc, le principe serait d'alléger le graphe (celui pour le problème de comparaison, défini en section~\ref{graph-definition}) en retirant des n\oe{}uds de celui-ci. \\

La première idée de simplification est de retirer les n\oe{}uds sur lesquels une contrainte de couleur est imposée. En effet, la comparaison de graphes n'est utile que pour attribuer aux n\oe{}uds qui sont une image dans la fonction de \textit{mapping} $M$, la couleur qu'ils avaient dans l'ancien graphe. Dès lors, si leur couleur est imposée par une contrainte, les comparer ne sert à rien: ils auront la couleur définie par la contrainte. De plus, comme les n\oe{}uds qui sont reliés entre eux doivent avoir la même couleur, on peut également retirer les n\oe{}uds qui sont reliés à des n\oe{}uds avec contrainte. Si nous prenons l'exemple du graphe donné en figure~\ref{compare_graph_ex}, la version simplifiée est représentée en figure~\ref{compare_graph_simpl} en imaginant qu'une contrainte de couleur est imposée aux n\oe{}uds 3 et 7. \\

\begin{figure}[h]
	\begin{center}
		\includegraphics[scale=0.3]{Images/compare_graph_simpl.pdf}
		\caption{Le graphe simplifié pour la comparaison}
		\label{compare_graph_simpl}
	\end{center}
\end{figure}

Une deuxième simplification qui réduit également le nombre de n\oe{}uds à comparer se base sur la structure du graphe. Comme vu en section~\ref{graph-definition}, le graphe pour le problème de comparaison est, en fait, un ensemble de composants connectés. Dès lors, nous pouvons imaginer de comparer chaque composant connecté un à un plutôt que de considérer tout le graphe. Illustrons cette idée à l'aide d'un exemple très simple. Imaginons que nous avons deux graphes, tous deux composés de deux composants connectés. Un tel graphe est représenté en figure~\ref{compare_graph_simpl_2}. \\

\begin{figure}[h]
	\begin{center}
		\includegraphics[scale=0.3]{Images/compare_graph_simpl_2.pdf}
		\caption{Un exemple de deux graphes avec composants connectés}
		\label{compare_graph_simpl_2}
	\end{center}
\end{figure}

L'idée serait de comparer en premier les composants connectés $A$ et $C$. Ensuite, nous ferions la comparaison entre les composants connectés $A$ et $D$, puis entre les composants connectés $B$ et $C$ et, enfin, entre les composants connectés $B$ et $D$. \\

En effet, supposons que nous ayons deux graphes contenant chacun $k$ composants connectés de $n$ n\oe{}uds (ce qui fait que les deux graphes contiennent $kn$ n\oe{}uds). Il y a $(kn)^2$ paires possibles pour l'ensemble de paires de n\oe{}uds \textit{matchés}, dans le cas où nous travaillons avec le graphe entier. Ce qui fait que nous avons en tout $2^{(kn)^2}$ choix à faire (pour chaque paire nous choisissons si elle va ou non dans l'ensemble). Dans le cas où nous traitons les graphes composantes par composantes, il faut d'abord choisir les séquences que l'on va comparer, nous avons $k^2$ possibilités. Ensuite, il existe, pour chaque couple de composantes connexes que l'on compare, $n^2$ paires possibles, donc $2^{n^2}$ choix possibles. En tout, nous obtenons $k^2 2^{n^2}$, ce qui est plus petit que $2^{k^2n^2}$.